\subsection{Descripcion}

Aqu\'{i} describiremos nuestro algoritmo para aplicar el filtro Sierpinski sobre una imagen, vali\'{e}ndonos de las instrucciones SIMD.

En primer lugar, por la naturaleza de las operaciones involucradas en este filtro, s\'{o}lo es posible procesar en paralelo un p\'{i}xel. En efecto, el filtro
viene dado por la siguiente f\'{o}rmula: 

\begin{equation*}
dst(i,j) = src(i,j)*coef(i,j)
\end{equation*}
donde: 
\begin{equation*}
coef(i,j) =  \frac{1}{255,0}(\lfloor \frac{i}{cant_{filas}}*255,0 \rfloor \oplus \lfloor \frac{j}{cant_{cols}}*255,0 \rfloor)
\end{equation*}

y justamente, como $coef(i,j)$ debe representarse en punto flotante para luego multiplicar los canales rojo, verde y azul por dicho coeficiente, es necesario
llevar los valores $r$,$g$ y $b$ a represetaci\'{o}n de punto flotante, con lo cual no puede procesarse m\'{a}s de un p\'{i}xel en paralelo, pues el ancho
de un registro multimedia es menor al tama\~{n}o que ocupar\'{i}an dos p\'{i}xeles con la precisi\'{o}n extendida a punto flotante de precisi\'{o}n simple, incluso
ignorando el canal alfa (en cuyo caso ocupar\'{i}an 6 double words, mientras que un registro multimedia s\'{o}lo entran 4).

Para procesar cada p\'{i}xel, debemos obtener, en primer lugar, $coef(i,j)$. Para calcularlo, debemos utilizar continuamente las instrucciones de 
conversi\'{o}n de datos, para pasar de entero a punto flotante y viceversa. En primer lugar, debemos obtener el valor $\frac{i}{cant_{filas}}$, para lo cual
debemos convertir tanto el $i$ como el $cant_{filas}$ a punto flotante para poder hacer la divisi\'{o}n. Luego, multiplicamos dicho resultado por la constante
(en punto flotante) $255.0$. An\'{a}logamente, hacemos las operaciones necesarias sobre $j$ y $cant_{cols}$, y pasamos estos dos resultados a representaci\'{o}n
entera, para hacer el \verb|xor| entre ellos. Una vez hecha la operaci\'{o}n l\'{o}gica, volvemos a castear a punto flotante y dividimos por la constante 
$255.0$, obteniendo finalmente $coef(i,j)$. As\'{i}, contamos con un registro multimedia de esta forma:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $coef(i,j)$& $*$ & $*$ & $*$ \\ \hline
   \end{tabular}
\end{center}

El siguiente paso es extender (dos veces) la precisi\'{o}n de los tres canales de p\'{i}xel fuente (es decir, desde byte hasta double word) y luego castear
dichos valores a float, para poder hacer el producto con $coef(i,j)$. Pero, para poder multiplicar todos los canales en paralelo, es necesario que $coef(i,j)$
est\'{e} ``repetido`` en el registro; esto es, deseamos que haya un registro con esta informaci\'{o}n guardada:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $coef(i,j)$& $coef(i,j)$ & $coef(i,j)$ & $0$ \\ \hline
   \end{tabular}
\end{center}

Esto podemos lograrlo f\'{a}cilmente, vali\'{e}ndonos de las operaciones de shift. En primer lugar, desplazamos 12 bytes a izquierda el registro con el 
$coef(i,j)$ en el primer float, quedando el registro de esta manera:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $0$& $0$ & $0$ & $coef(i,j)$ \\ \hline
   \end{tabular}
\end{center}

Volviendo a shiftear 12 bytes, esta vez hacia la derecha, el registro queda de esta manera:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $coef(i,j)$& $0$ & $0$ & $0$ \\ \hline
   \end{tabular}
\end{center}

Luego, forzando ceros en otro registro (que tambi\'{e}n puede hacerse con la operaci\'{o}n $pxor$), copiando el $coef(i,j)$ en el registro con ceros shifteando
4 bytes a izquierda, obtenemos un segundo registro as\'{i}:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $0$& $coef(i,j)$ & $0$ & $0$ \\ \hline
   \end{tabular}
\end{center}

y un $por$ entre el registro original y este obtenemos el $coef(i,j)$ en los dos primeros floats. Operando de forma an\'{a}loga se puede obtener el $coef(i,j)$
en el tercer float.

Una vez hecho esto, extendemos la precisi\'{o}n de cada canal del p\'{i}xel fuente (desempaquetando con ceros) hasta llegar a double word, y 
luego casteamos a float. Con lo hecho anteriormente tenemos, por un lado, el registro con el p\'{i}xel de entrada as\'{i}:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $float(b_0)$&$float(g_0)$ & $float(r_0)$ & $0$ \\ \hline
   \end{tabular}
\end{center}

y por otro lado:

\begin{center}
   \begin{tabular}{| l | c | r | c | r | c | r | c | r |c | r |c | r |}
     \hline
     $coef(i,j)$& $coef(i,j)$ & $coef(i,j)$ & $0$ \\ \hline
   \end{tabular}
\end{center}

con lo cual, lo que debemos hacer es el producto (en paralelo) de estos dos registros. Una vez hecho esto, s\'{o}lo resta volver a convertir los datos 
a representaci\'{o}n entera y empaquetarlos dos veces (con truncamiento) para volverlos a su tama\~{n}o original. En este punto vale la pena aclarar que,
si bien nuestro programa procesa un p\'{i}xel en paralelo, hemos decidido aprovechar la lectura de 16 bytes a la imagen fuente y procesar los 4 p\'{i}xeles
leidos dentro de la misma iteraci\'{o}n, con lo cual nuestro programa debe acomodar los p\'{i}xeles dentro de un registro (que contendr\'{a} la data que 
finalmente se mover\'{a} a la imagen destino) a medida que los procesa. Sin embargo, hemos decidido no incluir en esta descripci\'{o}n esa parte de los
algoritmos, pues no aportan a la comprensi\'{o}n de c\'{o}mo nuestro programa procesa cada p\'{i}xel.

\subsection{Experimentacion}

\subsubsection{Secuencial vs. Vectorial}

En este experimento queremos comprobar empiricamente la utilidad de usar SSE. Es decir, si para este tipo de filtro logramos una performance mejor a aquellas 
obtenidas de optimizaciones de codigo en lenguaje C.

\begin{figure}[H]
    \includegraphics[width=1\textwidth]{sierpinski14}
  \label{sierpinski14}
\end{figure}

Este gr\'{a}fico presenta la misma estructura que el realizado para el mismo experimento en el fitro CropFlip. Por lo tanto, la conclusi\'{o}n es la misma: en este tipo 
de procesamiento de datos, la utilizaci\'{o}n de c\'{o}digo Assembler es simplemente contrapruducente, dado que tenemos compiladores que nos proveen de 
optimizaciones con las cuales obtenemos una mejor perfonmance de la que nosotros podemos conseguir, con un programa cuyo c\'{o}digo es m\'{a} simple de escribir. Creemos que los resultados obtenidos
se deben a que, como explicamos en la descripci\'{o}n del filtro, nuestro algoritmo  (por la naturaleza del las operaciones aritm\'{e}ticas y l\'{o}gicas
que se debe hacer) no puede procesar m\'{a}s de un p\'{i}xel en paralelo, con lo cual el tiempo empleado en el procesamiento de los datos es parecido en las 
versiones de los filtros de C y de Assembler, si compilamos con flags de optimizaci\'{o}n para la versi\'{o}n de C.


\subsubsection{CPU vs. Bus de memoria}

En este experimento intentamos determinar cu\'{a}l es el factor limitante para la performance del filtro. Por lo tanto, tomamos mediciones para las mismas im\'{a}genes 
agregando distintos tipos de instruciones de operaciones aritm\'{e}ticas y accesos a memoria para lograr una variacion en la performance que nos permita decidir qu\'{e} 
tipo de instrucciones es el que influye de mayor manera en el tiempo de ejecuci\'{o}n.

\begin{figure}[H]
    \includegraphics[width=1\textwidth]{sierpinski15}
  \label{sierpinski14}
\end{figure}

Vemos en el gr\'{a}fico que no hay una variaci\'{o}n significativa en la performance para las instrucciones aritm\'{e}ticas, mientras que s\'{i} se presenta una para los accesos 
a memoria. Este resultado, m\'{a}s el obtenido anteriormente en el mismo experimento (para el filtro cropflip) nos da la idea de que el acceso a memoria pesa mucho m\'{a}s que el 
uso de intrucciones aritm\'{e}ticas.



